package main

import (
	"fmt"
)

/**
执行用时：12 ms, 在所有 Go 提交中击败了89.31%的用户
内存消耗：6.2 MB, 在所有 Go 提交中击败了29.96%的用户
 */
func jump(nums []int) int {

	n := len(nums)
	f := make([]int, n)
	f[0] = 0
	for i, j := 1, 0; i < n; i++ {
		for j + nums[j] < i { j++ }
		f[i] = f[j] + 1
	}
	return f[n - 1]
}

func main() {

	nums := []int{2, 3, 1, 1, 4}
	fmt.Println(jump(nums))  // 2
}
